<!--
 * @Author: JPeng 872639397@qq.com
 * @Date: 2022-05-23 11:36:36
 * @LastEditors: JPeng 872639397@qq.com
 * @LastEditTime: 2022-05-23 11:36:53
 * @FilePath: \review-review-review\复习！！！\leetcode\675砍树.html
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        var cutOffTree = function (forest) {
            let result = 0, m = forest.length, n = forest[0].length;
            let Tree = Array(m * n).fill(-1);
            for (let i = 0; i < m; i++) {
                for (let j = 0; j < n; j++) {
                    if (forest[i][j] > 1) Tree[forest[i][j]] = [i, j];
                }
            }
            Tree = Tree.filter(value => value !== -1);
            let step = [[-1, 0], [0, 1], [1, 0], [0, -1]];
            let nowstep = 0, min = 0;
            const dfs = function (x, y) {
                if (x === target[0] && y === target[1]) {
                    flag = true;
                    min = Math.min(nowstep, min);
                    return;
                }
                let num = forest[x][y];
                forest[x][y] = 0;
                nowstep++;
                for (let i = 0; i < step.length; i++) {
                    let newx = x + step[i][0];
                    let newy = y + step[i][1];
                    if (newx < m && newy < n && newx >= 0 && newy >= 0 && forest[newx][newy]) {
                        dfs(newx, newy);
                    }
                }
                forest[x][y] = num;
                nowstep--;
            }
            let target = Tree[0], flag = false;
            dfs(0, 0);
            if (!flag) return -1;
            result += min;
            for (let i = 1; i < Tree.length; i++) {
                flag = false, nowstep = 0, min = 0;
                target = Tree[i];
                dfs(Tree[i - 1][0], Tree[i - 1][1]);
                if (!flag) return -1;
                result += min;
            }
            return result;
        };
        console.log(cutOffTree([[1, 2, 3], [0, 0, 4], [7, 6, 5]]));
    </script>
</body>

</html>